//
// Created by yangchao on 2022/4/20.
// 5. 最长回文子串: https://leetcode-cn.com/problems/longest-palindromic-substring/
//

#include <string>
#include <vector>
using namespace std;

//动态规划
class LongestPalindrome {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if (len < 2) return s;
        int maxLen = 1;
        int begin = 0;
        //dp[i][j]表示s[i][j]是否是回文串
        vector<vector<int>> dp(len,vector<int>(len));
        //先枚举子串长度
        for (int j = 0; j < len; ++j) {
            for (int i = 0; i <= j; ++i) {
                if (s[i] == s[j] && (j-i < 3 || dp[i+1][j-1])) {
                    dp[i][j] = true;
                    if (j-i+1 > maxLen) {
                        //记录子串的长度和起始位置
                        maxLen = j-i+1;
                        begin = i;
                    }
                }
            }
        }
        return s.substr(begin,maxLen);
    }
};

